package com.zlk.algorithm.huawei.leetcode.dp;

/**
 * @program: algorithm
 * @ClassName Code50_maxProduct
 * @description:
 * 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
 * 子数组
 * （该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 *
 * 测试用例的答案是一个 32-位 整数。
 * 示例 1:
 * 输入: nums = [2,3,-2,4]
 * 输出: 6
 * 解释: 子数组 [2,3] 有最大乘积 6。
 * 示例 2:
 * 输入: nums = [-2,0,-1]
 * 输出: 0
 * 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 * @author: slfang
 * @create: 2025-01-16 09:11
 * @Version 1.0
 **/
public class Code50_maxProduct {

    // dp[i] 表示i位置结尾的最大子数组乘积
    // 1、dp[i-1] max * nums[i]
    // 2、dp[i-1] min * nums[i]
    // 3、 nums[i]
    public int maxProduct(int[] nums) {
        int premin = nums[0];
        int premax = nums[0];
        int ans = nums[0];
        for (int i = 1,curmin, curmax; i < nums.length; i++) {
            curmax = Math.max(Math.max(premax*nums[i],nums[i]),premin*nums[i]);
            curmin = Math.min(Math.min(premax*nums[i],nums[i]),premin*nums[i]);
            premax = curmax;
            premin = curmin;
            ans = Math.max(premax,ans);
        }
        return ans;
    }

    public int maxProduct1(int[] nums) {
        //dp[i] 表示i位置结尾的最大子数组乘积
        //向左发散，分析出以下三种情况
        // 可能性分析
        //1、 i >1  只取当前自己
        //2、 i >=1  dp[i-1]结尾最大值*nums[i]
        //3、 nums[i] <0   dp[i-1]结尾最小值*nums[i]
        int n = nums.length;
        //以i结尾的最最大值
        int[] dpMax = new int[n];
        //以i结尾的最小值
        int[] dpMin = new int[n];
        int max;
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        max = dpMax[0];
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            int p1 = dpMax[i-1]*num;
            int p2 = dpMin[i-1]*num;
            int maxDp = Math.max(p1,p2);
            int minDp = Math.min(p1,p2);
            dpMax[i] = Math.max(maxDp,num);
            dpMin[i] = Math.min(minDp,num);
            max = Math.max(max,dpMax[i]);
        }
        return max;
    }
}
